import type { Fragment } from "./fragment.ts";
import type { NodeType } from "./schema.ts";

type MatchEdge = { type: NodeType; next: ContentMatch };

///该类的实例表示节点类型的匹配状态
///[内容表达式](#model. nospecc .content)，并可用于
///查找是否有更多的内容匹配在这里，以及是否给定的
///位置是一个有效的节点结束。
export class ContentMatch {
  /// @internal
  next: MatchEdge[] = [];
  /// @internal
  wrapCache: (NodeType | NodeType[] | null)[] = [];
  validEnd: boolean;
  /// @internal
  constructor(
    validEnd: boolean,
  ) {
    this.validEnd = validEnd;
  }

  /// @internal
  static parse(
    string: string,
    nodeTypes: { [name: string]: NodeType },
  ): ContentMatch {
    const stream = new TokenStream(string, nodeTypes);
    if (stream.next == null) return ContentMatch.empty;
    const expr = parseExpr(stream);
    if (stream.next) stream.err("Unexpected trailing text");
    const match = dfa(nfa(expr));
    checkForDeadEnds(match, stream);
    return match;
  }

  matchType(type: NodeType): ContentMatch | null {
    for (let i = 0; i < this.next.length; i++) {
      if (this.next[i].type == type) return this.next[i].next;
    }
    return null;
  }

  matchFragment(
    frag: Fragment,
    start = 0,
    end = frag.content.length,
  ): ContentMatch | null {
    let cur: ContentMatch | null = this;
    for (let i = start; cur && i < end; i++) {
      cur = cur.matchType(frag.content[i].type);
    }
    return cur;
  }

  /**
   * 获取默认类型的第一个
   */
  get defaultType(): NodeType | null {
    for (let i = 0; i < this.next.length; i++) {
      const { type } = this.next[i];
      if (!type.hasRequiredAttrs()) return type;
    }
    return null;
  }

  compatible(other: ContentMatch): boolean {
    for (let i = 0; i < this.next.length; i++) {
      for (let j = 0; j < other.next.length; j++) {
        if (this.next[i].type == other.next[j].type) return true;
      }
    }
    return false;
  }

  get edgeCount(): number {
    return this.next.length;
  }

  edge(n: number): MatchEdge {
    if (n >= this.next.length) {
      throw new RangeError(` ${n} 超出了 ${this.next.length}`);
    }
    return this.next[n];
  }

  toString(): string {
    const seen: ContentMatch[] = [];
    function scan(m: ContentMatch) {
      seen.push(m);
      for (let i = 0; i < m.next.length; i++) {
        if (seen.indexOf(m.next[i].next) == -1) scan(m.next[i].next);
      }
    }
    scan(this);
    return seen.map((m, i) => {
      let out = i + (m.validEnd ? "*" : " ") + " ";
      for (let i = 0; i < m.next.length; i++) {
        out += (i ? ", " : "") + m.next[i].type.name + "->" +
          seen.indexOf(m.next[i].next);
      }
      return out;
    }).join("\n");
  }

  /// @internal
  static empty: ContentMatch = new ContentMatch(true);
}

class TokenStream {
  pos = 0;
  tokens: string[];
  nodeTypes: { [name: string]: NodeType };
  string: string;

  constructor(
    string: string,
    nodeTypes: { [name: string]: NodeType },
  ) {
    this.string = string;
    this.nodeTypes = nodeTypes;
    this.tokens = string.split(/\s*(?=\b|\W|$)/);
    if (this.tokens[this.tokens.length - 1] == "") this.tokens.pop();
    if (this.tokens[0] == "") this.tokens.shift();
  }

  get next() {
    return this.tokens[this.pos];
  }

  eat(tok: string) {
    return this.next == tok && (this.pos++ || true);
  }

  err(str: string): never {
    throw new SyntaxError(str + " (约束必须是 '" + this.string + "')");
  }
}

type Expr =
  | { type: "choice"; exprs: Expr[] }
  | { type: "seq"; exprs: Expr[] }
  | { type: "plus"; expr: Expr }
  | { type: "star"; expr: Expr }
  | { type: "opt"; expr: Expr }
  | { type: "range"; min: number; max: number; expr: Expr }
  | { type: "name"; value: NodeType };

function parseExpr(stream: TokenStream): Expr {
  const exprs = [];
  do {
    exprs.push(parseExprSeq(stream));
  } while (stream.eat("|"));
  return exprs.length == 1 ? exprs[0] : { type: "choice", exprs };
}

function parseExprSeq(stream: TokenStream): Expr {
  const exprs = [];
  do {
    exprs.push(parseExprSubscript(stream));
  } while (stream.next && stream.next != ")" && stream.next != "|");
  return exprs.length == 1 ? exprs[0] : { type: "seq", exprs };
}

function parseExprSubscript(stream: TokenStream): Expr {
  let expr = parseExprAtom(stream);
  for (;;) {
    if (stream.eat("+")) {
      expr = { type: "plus", expr };
    } else if (stream.eat("*")) {
      expr = { type: "star", expr };
    } else if (stream.eat("?")) {
      expr = { type: "opt", expr };
    } else if (stream.eat("{")) {
      expr = parseExprRange(stream, expr);
    } else break;
  }
  return expr;
}

function parseNum(stream: TokenStream) {
  if (/\D/.test(stream.next)) {
    stream.err("Expected number, got '" + stream.next + "'");
  }
  const result = Number(stream.next);
  stream.pos++;
  return result;
}

function parseExprRange(stream: TokenStream, expr: Expr): Expr {
  let min = parseNum(stream), max = min;
  if (stream.eat(",")) {
    if (stream.next != "}") max = parseNum(stream);
    else max = -1;
  }
  if (!stream.eat("}")) stream.err("Unclosed braced range");
  return { type: "range", min, max, expr };
}

function resolveName(stream: TokenStream, name: string): NodeType[] {
  const types = stream.nodeTypes, type = types[name];
  if (type) return [type];
  const result = [];
  for (const typeName in types) {
    const type = types[typeName];
    if (type.groups.indexOf(name) > -1) result.push(type);
  }
  if (result.length == 0) {
    stream.err("No node type or group '" + name + "' found");
  }
  return result;
}

function parseExprAtom(stream: TokenStream): Expr {
  if (stream.eat("(")) {
    const expr = parseExpr(stream);
    if (!stream.eat(")")) stream.err("Missing closing paren");
    return expr;
  } else if (!/\W/.test(stream.next)) {
    const exprs = resolveName(stream, stream.next).map((type) => {
      return { type: "name", value: type } as Expr;
    });
    stream.pos++;
    return exprs.length == 1 ? exprs[0] : { type: "choice", exprs };
  } else {
    stream.err("Unexpected token '" + stream.next + "'");
  }
}

// The code below helps compile a regular-expression-like language
// into a deterministic finite automaton. For a good introduction to
// these concepts, see https://swtch.com/~rsc/regexp/regexp1.html

type Edge = { term: NodeType | undefined; to: number | undefined };

/// Construct an NFA from an expression as returned by the parser. The
/// NFA is represented as an array of states, which are themselves
/// arrays of edges, which are `{term, to}` objects. The first state is
/// the entry state and the last node is the success state.
///
/// Note that unlike typical NFAs, the edge ordering in this one is
/// significant, in that it is used to contruct filler content when
/// necessary.
function nfa(expr: Expr): Edge[][] {
  const nfa: Edge[][] = [[]];
  connect(compile(expr, 0), node());
  return nfa;

  function node() {
    return nfa.push([]) - 1;
  }
  function edge(from: number, to?: number, term?: NodeType) {
    const edge = { term, to };
    nfa[from].push(edge);
    return edge;
  }
  function connect(edges: Edge[], to: number) {
    edges.forEach((edge) => edge.to = to);
  }

  function compile(expr: Expr, from: number): Edge[] {
    if (expr.type == "choice") {
      return expr.exprs.reduce(
        (out, expr) => out.concat(compile(expr, from)),
        [] as Edge[],
      );
    } else if (expr.type == "seq") {
      for (let i = 0;; i++) {
        const next = compile(expr.exprs[i], from);
        if (i == expr.exprs.length - 1) return next;
        connect(next, from = node());
      }
    } else if (expr.type == "star") {
      const loop = node();
      edge(from, loop);
      connect(compile(expr.expr, loop), loop);
      return [edge(loop)];
    } else if (expr.type == "plus") {
      const loop = node();
      connect(compile(expr.expr, from), loop);
      connect(compile(expr.expr, loop), loop);
      return [edge(loop)];
    } else if (expr.type == "opt") {
      return [edge(from)].concat(compile(expr.expr, from));
    } else if (expr.type == "range") {
      let cur = from;
      for (let i = 0; i < expr.min; i++) {
        const next = node();
        connect(compile(expr.expr, cur), next);
        cur = next;
      }
      if (expr.max == -1) {
        connect(compile(expr.expr, cur), cur);
      } else {
        for (let i = expr.min; i < expr.max; i++) {
          const next = node();
          edge(cur, next);
          connect(compile(expr.expr, cur), next);
          cur = next;
        }
      }
      return [edge(cur)];
    } else if (expr.type == "name") {
      return [edge(from, undefined, expr.value)];
    } else {
      throw new Error("Unknown expr type");
    }
  }
}

function cmp(a: number, b: number) {
  return b - a;
}

// Get the set of nodes reachable by null edges from `node`. Omit
// nodes with only a single null-out-edge, since they may lead to
// needless duplicated nodes.
function nullFrom(nfa: Edge[][], node: number): number[] {
  const result: number[] = [];
  scan(node);
  return result.sort(cmp);

  function scan(node: number): void {
    const edges = nfa[node];
    if (edges.length == 1 && !edges[0].term) return scan(edges[0].to!);
    result.push(node);
    for (let i = 0; i < edges.length; i++) {
      const { term, to } = edges[i];
      if (!term && result.indexOf(to!) == -1) scan(to!);
    }
  }
}

// Compiles an NFA as produced by `nfa` into a DFA, modeled as a set
// of state objects (`ContentMatch` instances) with transitions
// between them.
function dfa(nfa: Edge[][]): ContentMatch {
  const labeled: Record<string, ContentMatch> = {};
  return explore(nullFrom(nfa, 0));

  function explore(states: number[]) {
    const out: [NodeType, number[]][] = [];
    states.forEach((node) => {
      nfa[node].forEach(({ term, to }) => {
        if (!term) return;
        let set: number[] | undefined;
        for (let i = 0; i < out.length; i++) {
          if (out[i][0] == term) set = out[i][1];
        }
        nullFrom(nfa, to!).forEach((node) => {
          if (!set) out.push([term, set = []]);
          if (set && set.indexOf(node) == -1) set.push(node);
        });
      });
    });
    const state = labeled[states.join(",")] = new ContentMatch(
      states.indexOf(nfa.length - 1) > -1,
    );
    for (let i = 0; i < out.length; i++) {
      const states = out[i][1].sort(cmp);
      state.next.push({
        type: out[i][0],
        next: labeled[states.join(",")] || explore(states),
      });
    }
    return state;
  }
}

function checkForDeadEnds(match: ContentMatch, stream: TokenStream) {
  for (let i = 0, work = [match]; i < work.length; i++) {
    const state = work[i];
    let dead = !state.validEnd;
    const nodes = [];
    for (let j = 0; j < state.next.length; j++) {
      const { type, next } = state.next[j];
      nodes.push(type.name);
      if (dead && !type.hasRequiredAttrs()) dead = false;
      if (work.indexOf(next) == -1) work.push(next);
    }
    if (dead) stream.err("节点类型和约束不一致 (" + nodes.join(", ") + ")");
  }
}
